'''
两个链表的第一个公共节点，即寻找两个链表的公共节点
'''


class ListNode:
    def __init__(slef,x):
        slef.val = x
        slef.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        '''
            思路1
                分别遍历两个链表求两个链表的长度，然后相减得出差值，然后长一点的链表先走完差值的步数，
                即两个链表都是在同样的起点，当相遇时刻就是公共节点
        '''
        la,lb = 0,0
        p,q = headA,headB
        while p:
            p = p.next
            la += 1
        while q:
            q = q.next
            lb += 1
        diff = la - lb
        p,q = headA,headB
        if diff > 0:
            for i in range(la - lb):
                p = p.next
        else:
            for i in range(lb - la):
                q = q.next
        while p != q:
            p = p.next
            q= q.next
        return p
    
    def getIntersectionNode2(self, headA: ListNode, headB: ListNode) -> ListNode:
        '''
            思路2
                假设两个链表的公共长度为c，其余长度分别为a,b，则加起来的长度则为a+b+c，即同时遍历两个链表，当遍历完A链表，将B链表链接到A链表后面，
                同理，B链表也这样。则同时遍历完a+b+c的长度，再次到公共长度时，即为相遇的节点
        '''
        p,q = headA,headB
        while p != q:
            if p == None:
                p = headB
            else:
                p = p.next
            
            if q == None:
                q = headA
            else:
                q = q.next
        return p
            